// 152.乘积最大子数组
package LeetcodeHot100;

public class Solution152 {
    public int maxProduct(int[] nums) {
        int[] dp_max = new int[nums.length];
        int[] dp_min = new int[nums.length];

        dp_max[0] = nums[0];
        dp_min[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            dp_max[i] = Math.max(Math.max(nums[i], nums[i] * dp_max[i - 1]), nums[i] * dp_min[i - 1]);
            dp_min[i] = Math.min(Math.min(nums[i], nums[i] * dp_max[i - 1]), nums[i] * dp_min[i - 1]);
        }

        int result = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            result = Math.max(result, dp_max[i]);
        }
        return result;
    }
}
